package a00_LeetCode.Stack;

import java.util.Stack;

/**
 * @Author quan
 * @Description 给定两个序列，判断第二个序列是不是第一个的出栈情况
 * @Date 2023/3/22 15:06
 */
public class Num31_Offer_isValidSquence {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        //创建一个栈
        Stack<Integer> stack = new Stack<>();
        //i是s2的指针，从第一个值开始不断移动
        int i = 0;
        //遍历s1的值不断压入栈，直到s1的栈顶元素和s2的第一个值相等，则s1弹出栈顶元素
        for (int val : pushed) {
            stack.push(val);
            //注意：用的是while循环不是if,同时此时要注意前提条件：栈里面不能为空
            while (!stack.isEmpty() && popped[i] == stack.peek()){//s1的栈顶值和s2的指针指向的值相等
                stack.pop();//弹出s1的栈顶值
                i++;//s2的指针不断移动
            }
        }
        //直到for循环结束也就是s1所有的值都已经压入完栈了，但是此时栈中的值非空，则说明s2不是s1对应的出栈情况
        if(stack.isEmpty()){
            return true;
        }else{
            return false;
        }
    }
}
